package org.hhchat.leetcode.banarySearch;

/**
 * Created this one by HMH on 2017/9/29.
 */
public class code441_easy {

    static class Solution {
        public int arrangeCoins(int n) {
            if(n==0) return 0;
            int index = binsearch(n);
            if (index > 0) {
                return index;
            }
            else{
                return (-(index + 1)) - 1;
            }
        }

        public int binsearch(int count) {
            int l = 0;
            int h = count;
            while (l <= h) {
                int mid = (l + (h - l) / 2);
                double countNeed = getCount(mid);
                if (countNeed < count) {
                    l = mid + 1;
                } else if (countNeed > count) {
                    h = mid - 1;
                }else{
                    return mid;
                }
            }
            return -(l + 1);
        }

        public double getCount(double n) {
            System.out.println("---" + n);
            System.out.println((n*(n+1)/2));
            System.out.println((n*n)/2+n/2);
            return (n * n)/2 + n / 2;
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.arrangeCoins(5));
    }

}


/*
    simple math method solution

    return (int)((-1 + Math.sqrt(1 + 8 * (long)n)) / 2);

 */